package cn.mayday.algorithms.year2021.month1.C双指针专题;

/**
 * 简单
 * <p>
 * 剑指 Offer 25. 合并两个排序的链表
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * <p>
 * 示例1：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 * @description: TODO
 * @author: mayday
 * @date: 2021/5/12 22:33
 * @version: 1.0
 */
public class Offer025MergeTwoListsCopy {

    public static void main(String[] args) {

    }

    ListNode result;

    /**
     * 方法一：考察链表和双指针，不过这里双指针以及提前设计好,两个节点指针交替前进
     * 时间复杂度：M+N
     * 空间复杂度：节点引用 helpHeadNode , currentNode 使用常数大小的额外空间。
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        // 【重要】定义一个辅助头节点，这里因为没有头结点，注意这是辅助，最后读取它的next即可
        ListNode helpHeadNode = new ListNode(0);

        ListNode currentNode = helpHeadNode;

        // 如果两个都不为空
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                currentNode.next = l1;
                l1 = l1.next;
            } else {
                currentNode.next = l2;
                l2 = l2.next;
            }
            currentNode = currentNode.next; // 注意这个节点循环next一次
        }
        // 如果有一个为null,剩余的直接补齐即可
        if (l1 == null) {
            currentNode.next = l2;
        } else {
            currentNode.next = l1;
        }

        return helpHeadNode.next; // 注意头结点的next即为完整的节点
    }

    /**
     * 方法二：采用递归实现-----思考下分治就好了,每次去除当前比较的节点
     *
     * 时间复杂度：M+N
     * 空间复杂度：栈的深度 M+N
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            // 进行下一次递归，并将结果指向下一个递归结果
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
